package MultiSourceShortestPath;

import java.util.*;

public class Matrix {
    public int[][] updateMatrix(int[][] mat) {
        // 辅助向量数组
        int[] dx = { 1, -1, 0, 0 };
        int[] dy = { 0, 0, -1, 1 };

        int m = mat.length; // 对应 x 坐标
        int n = mat[0].length; // 对应 y 坐标

        int[][] dp = new int[m][n]; // 结果数组
        for (int[] row : dp) {
            // 所有元素默认设为 -1, 表示元素还没有访问到
            Arrays.fill(row, -1);
        }

        // 遍历数组, 获取到所有 0 的格子的坐标, 放到一个数组里面
        List<int[]> coord = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    // 为 0 的位置是起点,不应该设置成-1,而是 0
                    dp[i][j] = 0;
                    coord.add(new int[] { i, j });
                }
            }
        }

        // 将这些起点都放入队列中
        Queue<int[]> queue = new LinkedList<>();
        for (int[] point : coord) {
            queue.offer(point);
        }

        while (!queue.isEmpty()) {
            // 同时向外扩, 因此本道题没必要维护一个 size 来控制层数

            // 取出原点
            int[] point = queue.poll();
            int Ox = point[0];
            int Oy = point[1];

            // 遍历下一层节点
            for (int i = 0; i < 4; i++) {
                int x = Ox + dx[i];
                int y = Oy + dy[i];

                if (x >= 0 && x < m && y >= 0 && y < n && dp[x][y] == -1) {
                    if (mat[x][y] == 1) {
                        // 遇到 `1`, 更新结果
                        dp[x][y] = dp[Ox][Oy] + 1;
                    }
                    queue.offer(new int[] { x, y });
                }
            }
        }
        return dp;
    }
}
